package com.nine.algorithm.leetcode.list;

/**
 * @author nine
 * @version 1.0
 * @description 合并多个有序链表【多路递归，分而治之】
 * @date 24/5/5 17:46
 */
public class Leetcode023 {

	/**
	 * 定义指针，合并两个链表
	 *
	 * @param p1
	 * @param p2
	 * @return
	 */
	public static ListNode mergeTwoLists(ListNode p1, ListNode p2) {
		// 初始哨兵节点【此节点不能动，可以新增指针，指向这个，动指针即可】
		ListNode s = new ListNode(-1, null);
		ListNode p = s;
		while (p1 != null && p2 != null) {
			if (p1.val < p2.val) {
				p.next = p1;
				p1 = p1.next;
			}
			else {
				p.next = p2;
				p2 = p2.next;
			}
			p = p.next;
		}

		if (p1 != null) {
			p.next = p1;
		}
		else if (p2 != null) {
			p.next = p2;
		}

		return s.next;
	}

	public static ListNode mergeKList(ListNode[] lists) {
		if (lists.length == 0) {
			return null;
		}
		return split(lists, 0, lists.length - 1);
	}

	/**
	 * 返回合并之后的链表
	 *
	 * @param lists
	 * @param i     左边界
	 * @param j     右边界
	 * @return
	 */
	private static ListNode split(ListNode[] lists, int i, int j) {
		// 数组内只有一个链表
		if (i == j) {
			return lists[i];
		}
		int m = (i + j) >>> 1;
		ListNode left = split(lists, i, m);
		ListNode right = split(lists, m + 1, j);
		return mergeTwoLists(left, right);
	}

	public static void main(String[] args) {
		ListNode[] lists = {ListNode.of(1, 3, 4), ListNode.of(1, 4, 5), ListNode.of(2, 6)};
		System.out.println(mergeKList(lists));
	}

}
